Masala #1088

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 98 %
14

  

Naqshlar

Sizda \(N \times M\) katakchalardan iborat maydon bor, bu maydonda ba’zi  katakchalar kulrang rangda bo’yalgan va qolgan katakchalar bo’sh. Siz shu bo’sh kataklarni quyidagi 9 turdagi naqshlardan xoxlaganingizcha foydalanib to’ldirishingiz kerak:

Yagona shart naqshlarni burish mumkin emas, ya’ni 3-turdagi naqshni burgan holda 4-turdagi naqsh shaklini hosil qilib bo’lmaydi. 

Misol uchun quyidagi \(4 \times 3\) maydonni 6 xil usulda naqshlar bilan to’ldirish mumkin:

Sizga \(N \times M\) maydonning dastlabki holati berilgan, siz bu maydonga naqshlarni necha xil usulda joylashtirib to’ldirish mumkinligini aniqlang.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkida butun son, \(N(1 \leq N \leq 40)\)va \(M(1 \leq M \leq 8)\) sonlari berilgan. Keyingi \(N\) ta satrda \(M\)  ta butun son, 0 yoki 1 sonlari kiritiladi, bunda 0 bo’sh katakchani, 1 esa kulrang katakchani ifodalaydi.


Chiquvchi ma'lumotlar:

Chiqish faylining yagona satrida bitta butun son, berilgan maydonga naqshlarni necha xil usulda joylashtirib to’ldirish mumkinligini chop eting.


Misollar
# input.txt output.txt
1
4 3
1 0 0
0 0 1
0 0 1
1 1 1
6
2
2 2
0 0
0 0
4
3
1 8
0 0 0 0 0 0 0 0
1
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin